#include<bits/stdc++.h>
using namespace std;

class MedianFinder {
public:
    multiset<double>st;
    multiset<double> :: iterator medium;
    MedianFinder() {

    }
    
    void addNum(int num) {
        st.insert(num);
        if(st.size() == 1)medium = st.begin();
        else if(st.size() % 2 && num >= *medium)medium++;
        else if(!(st.size() % 2) && num < *medium)medium--;
    }
    
    double findMedian() {
        if(st.size() % 2) return *medium;
        double res = *medium;
        medium++;
        res += *medium;
        medium--;
        res /= 2;
        return res;
    }
};

/**
 * 2021.8.27
 * 可以用 multset 来维护数字，用一个指针始终指向中间位置（向下取整）
 * 在插入一个数字后：
 *      如果有奇数个数字而且新插入的数字 >= 我们指针指向的数字那么指针 ++;
 *      如果有偶数个数字而且新插入的数字 <  我们指针指向的数字那么指针 --;
 * 在任何时刻，指针指向的数字（奇数个的情况）或者指针指向的数字和下一个数字和的一半（偶数个的情况）
 * 就是中位数。
 */